package com.sort;

import java.util.Scanner;

/**
 * @author XiaoPan
 * date: 2022/3/19 21:52
 * <p>
 * action:
 */
public class textQuickSort {
    static Scanner sc = new Scanner(System.in);

    static void select_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int k = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[k] > arr[j]) {
                    k = j;
                }
            }
            if (k != i) {
                int temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
            }
        }
    }

    static void bubble_sort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] < arr[j + 1]) {
                    flag = true;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (flag == false) {
                break;
            }
        }
    }

    // 计数排序
    public static int[] countSort(int[] arr) {
        int maxN = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxN) {
                maxN = arr[i];
            }
        }
        int[] countArray = new int[maxN + 1];
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i]]++;
        }
        int index = 0;
        int[] sortArray = new int[arr.length];
        for (int i = 0; i < countArray.length; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                sortArray[index++] = i;
            }
        }
        return sortArray;
    }

    // 桶排序
    public static void t_sort(int[] arr, int n) {
        for (int i = 0; i < n; i++) {
            int key = sc.nextInt();
            arr[key]++;
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i]; j++) {
                System.out.print(i + " ");
            }
        }
    }

    //    public static void insert_sort(int[] arr) {
    //        for (int i = 0; i < arr.length; i++) {
    //            int x = arr[i];
    //            int j = i - 1;
    //            while (j >= 0 && x < arr[j]) {
    //                arr[j + 1] = arr[j];
    //                j--;
    //            }
    //            arr[j + 1] = x;
    //        }
    //    }

    public static void insert_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int x = arr[i];
            int j = i - 1;
            while (j >= 0 && x < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = x;
        }
    }

    // 快速排序
    public static void q_sort(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low >= high) {
            return;
        }
        i = low;
        j = high;
        temp = arr[low];
        while (i < j) {
            while (temp <= arr[j] && i < j) {
                j--;
            }
            while (temp >= arr[i] && i < j) {
                i++;
            }
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
        }
        arr[low] = arr[i];
        arr[i] = temp;
        q_sort(arr, low, j - 1);
        q_sort(arr, j + 1, high);
    }

    // 另一种
    public static void q2_sort(int[] arr, int low, int high) {
        int i, j, temp;
        temp = arr[low];
        i = low + 1;
        j = high;
        while (true) {
            while (i < j && temp >= arr[i]) {
                i++;
            }
            while (i < j && temp <= arr[j]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            arr[low] = arr[j];
            arr[j] = temp;
            q2_sort(arr, low, j - 1);
            q2_sort(arr, j + 1, high);



        }
    }

    // 归并排序
    public static void merge_sort(int[] arr, int[] temp, int left, int right) {
        int center = (left + right) / 2;
        merge_sort(arr, temp, left, center);
        merge_sort(arr, temp, center + 1, right);
        merge(arr, temp, left, center, right);
    }

    public static void merge(int[] arr, int[] temp, int left, int mid, int right) {
    }

    public static void main(String[] args) {
        // 选择排序
        //        int[] arr = new int[] {5, 4, 6, 8, 7, 1, 2, 3};
        //        select_sort(arr);
        //        for (Object c : arr) {
        //            System.out.println(c + " ");
        //        }

        // 冒泡排序
        //        int[] arr = new int[] {5, 4, 6, 8, 7, 1, 2, 3};
        //        bubble_sort(arr);
        //        for (Object c : arr) {
        //            System.out.println(c + " ");
        //        }

        // 桶排序
        //        int maxN = 10;
        //        int[] arr = new int[maxN];
        //        int n = sc.nextInt();
        //        t_sort(arr, n);
        //        计数
        //        int[] array = new int[] {4, 4, 6, 5, 3, 2, 8, 1, 7, 5, 6, 0, 10};
        //        int[] b = countSort(array);
        //        System.out.println(Arrays.toString(b));

        // 插入
        //        int[] arr = new int[] {0, 3, 2, 4, 1, 6, 5, 2, 7};
        //        int[] arr = new int[10];
        //        for (int i = 0; i < arr.length; i++) {
        //            arr[i] = sc.nextInt();
        //        }
        //        insert_sort(arr);
        //        System.out.println(Arrays.toString(arr));

        // 快速排序
        //        int[] arr = new int[] {0, 3, 2, 4, 1, 6, 5, 2, 7};
        //        q_sort(arr, 0, arr.length - 1);
        //        for (Object c : arr) {
        //            System.out.print(c + " ");
        //        }

        //
        //        Integer[] intArray = new Integer[] {2, 1, 3, -2};
        //        //        Arrays.sort(intArray);
        //        Arrays.sort(intArray, Collections.reverseOrder());
        //        for (Object c : intArray) {
        //            System.out.print(c + " ");
        //        }

        //        String[] s = {"x", "a", "B"};
        //        Arrays.sort(s);
        //        for (Object c : s) {
        //            System.out.print(c + " ");
        //        }

        //        LinkedList<Integer> l = new LinkedList<>();
        //        l.add(11);
        //        l.add(33);
        //        l.add(9);
        //        Collections.sort(l, Collections.reverseOrder());
        //        Iterator<Integer> it = l.iterator();
        //        while (it.hasNext()) {
        //            int i = it.next();
        //            System.out.println(i);
        //        }

        // 练习
        //        int N = sc.nextInt();
        //        long[] arr = new long[N];
        //        for (int i = 0; i < arr.length; i++) {
        //            arr[i] = sc.nextLong();
        //        }
        //        Arrays.sort(arr);
        //        for (int i = 0; i < arr.length; i++) {
        //            System.out.print(arr[i] + " ");
        //        }
        //        System.out.println();
        //        for (int i = arr.length - 1; i >= 0; i--) {
        //            System.out.print(arr[i] + " ");
        //        }

        //
        int[] arr = {20, 66, 55, -66, 90, 33, 66, 5151, 696, 10};
        System.out.print("排序前:");
        for (Object c : arr) {
            System.out.print(c + "\t");
        }
        q_sort(arr, 0, arr.length - 1);
        System.out.println();
        for (Object c : arr) {
            System.out.print(c + "\t");
        }
    }
}


